package com.dbh.alg.datastructure.priorityqueue;

import com.dbh.alg.datastructure.queue.Queue;

/**
 * 优先级队列
 * @param <E>
 */
public class PriorityQueue1<E extends Priority> implements Queue<E> {

    Priority[] array;

    int size;

    public PriorityQueue1(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[size++] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int index = selectMax();
        E e = (E) array[index];
        removeMaxPriorityIndex(index);
        return e;
    }

    private void removeMaxPriorityIndex(int index) {
        System.arraycopy(array, index + 1, array, index, size - index - 1);
        array[size-1] = null;
        size--;
    }

    /**
     * 找到优先级最大的元素索引
     * @return 优先级最大的元素索引
     */
    private int selectMax() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int index = selectMax();
        return (E) array[index];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    public static void main(String[] args) {
        Task task1 = new Task(1);
        Task task2 = new Task(2);
        Task task4 = new Task(4);
        Task task3 = new Task(3);
        PriorityQueue1<Task> priorityQueue1 = new PriorityQueue1<Task>(4);
        priorityQueue1.offer(task1);
        priorityQueue1.offer(task2);
        priorityQueue1.offer(task4);
        priorityQueue1.offer(task3);
        System.out.println(priorityQueue1.poll().priority());;
        System.out.println(priorityQueue1.poll().priority());;
        System.out.println(priorityQueue1.poll().priority());;
        System.out.println(priorityQueue1.poll().priority());;
    }
}
